// 你是一个专业的小偷，计划 偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
// 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
// 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
// 当前房屋偷与不偷，取决于前一个房屋和前两个房屋是否被偷

// 思路，动态规划
// 1. `dp[i]`,表示i以内的房屋，最多可以偷窃的金额
// 2. 确定递推公式，`dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1])`
// 3. 确定初始值，`dp[0] = nums[0];dp[1] = Math.max(nums[0], nums[1])`
// 4. 确定遍历顺序，从前到后
// 5. 举例推导

function rob(nums) {
    let dp = new Array(nums.length).fill(0)
    dp[0] = nums[0]
    dp[1] = Math.max(nums[0], nums[1])
    for (let i = 2; i <= nums.length; i++) {
        dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])        
    }
    return dp[nums.length - 1]
}

console.log(rob([2,7,9,3,1]))